Search results for "Transposition array"

showing 1 items of 1 documents

Gray code for permutations with a fixed number of cycles

2007

AbstractWe give the first Gray code for the set of n-length permutations with a given number of cycles. In this code, each permutation is transformed into its successor by a product with a cycle of length three, which is optimal. If we represent each permutation by its transposition array then the obtained list still remains a Gray code and this allows us to construct a constant amortized time (CAT) algorithm for generating these codes. Also, Gray code and generating algorithm for n-length permutations with fixed number of left-to-right minima are discussed.

Golomb–Dickman constantPolynomial codeRestricted permutationsGenerating algorithms0102 computer and information sciences02 engineering and technology01 natural sciencesTheoretical Computer ScienceGray codeCombinatoricsPermutation[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]0202 electrical engineering electronic engineering information engineeringDiscrete Mathematics and CombinatoricsTransposition arrayComputingMilieux_MISCELLANEOUSMathematicsDiscrete mathematicsSelf-synchronizing codeAmortized analysisMathematics::CombinatoricsParity of a permutation020206 networking & telecommunicationsGray codes010201 computation theory & mathematicsConstant-weight codeMathematicsofComputing_DISCRETEMATHEMATICS
researchProduct